//
// Description: 714. 买卖股票的最佳时机含手续费
// Created by Loading on 2022/6/25.
//

#include <bits/stdc++.h>

using namespace std;

int maxProfit(vector<int> &prices, int fee) {
    int n = prices.size();

    // dp[i][0] 表示第 i 天结束后，手里没有持有股票的最大收益
    // dp[i][1] 表示第 i 天结束后，手里仍持有股票的最大收益
    int dp[n][2];
    memset(dp, 0, sizeof dp);

    dp[0][1] = -prices[0];
    for (int i = 1; i < n; ++i) {
        // 状态转移
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    return dp[n - 1][0];
}

int main() {
    vector<int> prices{1, 3, 7, 5, 10, 3};
    int fee = 6;

    int res = maxProfit(prices, fee);

    cout << res << endl;

    return 0;
}
